package lucky.xiong.dataStructure.heap;

import java.util.Arrays;

/**
 * 堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看作一棵完全二叉树的数组对象。
 * <a href="https://www.runoob.com/data-structures/heap-storage.html">堆的基本存储、堆排等</a>
 * <a href="https://visualgo.net/zh/heap">在线动态数据结构，可以结合生成的堆动态查看</a>
 * @author xiongjianlin
 * <p>
 * 一、堆满足下列性质：
 * 堆中某个节点的值总是不大于或不小于其父节点的值。
 * 堆总是一棵完全二叉树。
 * 二、适用说明
 * 一般的操作进行一次的时间复杂度在 O(1)~O(logn) 之间，
 * 堆通常用于动态分配和释放程序所使用的对象。
 * 若为优先队列的使用场景，普通数组或者顺序数组，最差情况为 O(n^2)，
 * 堆这种数据结构也可以提高入队和出队的效率。
 */
public class Heap<T> {
    protected T[] data;
    /**
     * 元素个数
     */
    protected int count;

    /**
     * 返回当前的元素个数
     *
     * @return
     */
    public int getCount() {
        return count;
    }

    /**
     * 返回当前的树的最大节点数
     */
    public int size() {
        return data.length;
    }


    /**
     * 返回一个布尔值，表示堆中是否为空
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 交换堆中的两个元素
     */
    protected void swap(int index1, int index2) {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    @Override
    public String toString() {
        return "Heap{" +
                "data=" + Arrays.toString(data) +
                '}';
    }
}
